#define _CRT_SECURE_NO_WARNINGS 1

int searchInsert(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return left;
}

int mySqrt(int x) {
    int left = 0;
    int right = x;

    while (left <= right)
    {
        long mid = (left + right) / 2;
        if ((mid * mid) == x)
        {
            return mid;
        }
        else if ((mid * mid) < x)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return right;
}

int missingNumber(int* nums, int numsSize) {
    int ret = numsSize;
    for (int i = 0; i < numsSize; i++)
    {
        ret ^= i ^ nums[i];
    }
    return ret;
}

int firstBadVersion(int n) {
    int left = 1;
    int right = n;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid))
        {
            right = mid - 1;

        }
        else
        {
            left = mid + 1;
        }
    }
    return left;
}

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1;
}


int cmp(const void* a, const void* b)
{
    return *((int*)a) - *((int*)b);
}

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    qsort(nums1, nums1Size, sizeof(int), cmp);
    qsort(nums2, nums2Size, sizeof(int), cmp);
    int index1 = 0;
    int index2 = 0;
    int min = nums1Size < nums2Size ? nums1Size : nums2Size;
    int* ret = (int*)malloc(sizeof(int) * min);
    int n = 0;
    while (index1 < nums1Size && index2 < nums2Size)
    {
        if (nums1[index1] < nums2[index2])
        {
            index1++;
        }
        else if (nums1[index1] > nums2[index2])
        {
            index2++;
        }
        else {
            ret[n++] = nums1[index1];
            index1++;
            index2++;
        }
    }
    *returnSize = n;
    return ret;
}